/**
 * 如果用暴力法，每次节点遍历时间n*n，遍历所有的节点也为n*n,时间复杂度为n的四次方
 * 下述实现，通过记录每一块岛屿的编号，维护编号的面积。再访问节点为0时，加上各个岛屿的面积，返回最大面积。时间复杂度为n*n
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function (grid) {
    let visited = new Array(grid.length).fill(0).map(() => new Array(grid.length).fill(false)),
        maxArea = 0,
        mark = 2,
        markArea = new Map();

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid.length; j++) {
            if (grid[i][j] === 1 && visited[i][j] === false) {
                markArea.set(mark, dfs(grid, visited, i, j, mark, 1))
                maxArea = Math.max(maxArea, markArea.get(mark))
                mark++
            }
        }
    }

    let sum
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid.length; j++) {
            sum = 1
            if (grid[i][j] === 0) {
                let direction = [[1, 0], [-1, 0], [0, 1], [0, -1]],
                    hadSumKey = new Set();
                for (let [left, right] of direction) {
                    let newI = i + left,
                        newJ = j + right;
                    if (newI < 0 || newI >= grid.length || newJ < 0 || newJ >= grid.length) continue
                    if (!hadSumKey.has(grid[newI][newJ])) {
                        sum += markArea.get(grid[newI][newJ]) || 0
                    }
                    hadSumKey.add(grid[newI][newJ])
                }
            }
            maxArea = Math.max(maxArea, sum)
        }
    }
    return maxArea
};

function dfs(grid, visited, i, j, mark, area) {
    visited[i][j] = true
    grid[i][j] = mark
    let direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    for (let [left, right] of direction) {
        let newI = i + left,
            newJ = j + right;
        if (newI < 0 || newI >= grid.length || newJ < 0 || newJ >= grid.length) continue
        if (grid[newI][newJ] === 1 && visited[newI][newJ] === false) {
            area = dfs(grid, visited, newI, newJ, mark, area + 1)
        }
    }
    return area
}